package com.zyk.grate_offer.class04;

import java.util.*;

/**
 * 数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)
 * 意思是在数组里下标0~3这个范围上，有几个2？答案返回2。
 * 假设给你一个数组arr，
 * 对这个数组的查询非常频繁，都给出来
 * 请返回所有查询的结果
 *
 * @author zhangsan
 * @date 2021/4/28 15:47
 */
public class Code01_QueryHobby {

    // 暴力解
    public static class QueryBox1 {

        int[] arr;

        public QueryBox1(int[] arr) {
            this.arr = new int[arr.length];
            System.arraycopy(arr, 0, this.arr, 0, arr.length);
        }

        public int query(int L, int R, int V) {
            int cnt = 0;
            while (L <= R) {
                if (arr[L] == V) {
                    cnt++;
                }
                L++;
            }
            return cnt;
        }
    }

    // 预处理结构: 需要经常在L~R范围查V的个数
    // 预处理每个V的下标list, 在这个list里左二分, 即可快速确定L~R的位置. 相减即使答案
    public static class QueryBox2 {

        Map<Integer, List<Integer>> indexMap;

        public QueryBox2(int[] arr) {
            indexMap = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                if (!indexMap.containsKey(arr[i])) indexMap.put(arr[i], new ArrayList<>());
                indexMap.get(arr[i]).add(i);
            }
        }

        public int query(int L, int R, int V) {
            if (!indexMap.containsKey(V)) return 0;
            List<Integer> indexList = indexMap.get(V);
            int a = countLess(indexList, L);
            int b = countLess(indexList, R + 1);
            return b - a;
        }

        // 找到<limit的数中最右的位置
        private int countLess(List<Integer> arr, int limit) {
            int L = 0;
            int R = arr.size() - 1;
            int mostRight = -1;
            while (L <= R) {
                int mid = L + ((R - L) >> 1);
                if (arr.get(mid) < limit) {
                    mostRight = mid;
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            return mostRight + 1;
        }
    }


    public static int[] generateRandomArray(int len, int value) {
        int[] ans = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (int) (Math.random() * value) + 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        int len = 30;
        int value = 20;
        int testTimes = 1000;
        int queryTimes = 1000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(len, value);
            int N = arr.length;
            QueryBox1 box1 = new QueryBox1(arr);
            QueryBox2 box2 = new QueryBox2(arr);
            for (int j = 0; j < queryTimes; j++) {
                int a = (int) (Math.random() * N);
                int b = (int) (Math.random() * N);
                int L = Math.min(a, b);
                int R = Math.max(a, b);
                int v = (int) (Math.random() * value) + 1;
                if (box1.query(L, R, v) != box2.query(L, R, v)) {
                    System.out.println("Oops!");
                    System.out.println(Arrays.toString(arr));
                    System.out.println("L: " + L);
                    System.out.println("R: " + R);
                    System.out.println("V: " + v);
                    System.out.println(box1.query(L, R, v));
                    System.out.println(box2.query(L, R, v));
                    break;
                }
            }
        }
        System.out.println("test end");
    }
}
